package com.leet.tree;

import java.util.ArrayList;
import java.util.List;

public class RecoverTree {
    List<TreeNode> list = new ArrayList<>();
    TreeNode pre = null;
    TreeNode post = null;
    public void recoverTree(TreeNode root) {
        inOrder(root);
        // 答案为第一个的最大值和最后一个的最小值
        for(int i = 0; i < list.size(); i++){
            if(list.get(i).val > list.get(i+1).val){
                if(pre == null) pre = list.get(i);
                post = list.get(i+1);
            }
        }
        if(pre != null && post != null){
            int tmp = pre.val;
            pre.val = post.val;
            post.val = tmp;
        }
    }
    public void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        list.add(root);
        inOrder(root.right);
    }
}
